/*
 * @lc app=leetcode.cn id=833 lang=cpp
 * @lcpr version=30204
 *
 * [833] 字符串中的查找与替换
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution
{
public:
    string findReplaceString(string s, vector<int> &indices, vector<string> &sources, vector<string> &targets)
    {
        int n = s.length();
        vector<pair<string, int>> replace(n, {"", 1}); // 无需替换时 i+=1
        for (int i = 0; i < indices.size(); i++)
            if (s.compare(indices[i], sources[i].length(), sources[i]) == 0)
                replace[indices[i]] = {targets[i], sources[i].length()}; // {替换后的字符串，被替换的长度}

        string ans;
        for (int i = 0; i < n; i += replace[i].second)
        { // 无需替换时 i+=1
            if (replace[i].first.empty())
            {
                ans += s[i];
            }
            else
            {
                ans += replace[i].first;
            }
        }
        return ans;
    }
};
// @lc code=end

/*
// @lcpr case=start
// "abcd"\n[0,2]\n["a","cd"]\n["eee","ffff"]\n
// @lcpr case=end

// @lcpr case=start
// "abcd"\n[0,2]\n["ab","ec"]\n["eee","ffff"]\n
// @lcpr case=end

 */
